package com.azdebugit.java8.suanfa;

import java.util.*;

class SolutionBb {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> resList = new ArrayList<>();
        Deque<Integer> numS = new ArrayDeque<>();
        dfs(candidates,target,candidates[candidates.length-1],numS,resList);
        return resList;
    }

    public void dfs(int[] candidates, int target,int max, Deque<Integer> numS,List<List<Integer>> resList){
        if(target==0){
            resList.add(new ArrayList<>(numS));
            return;
        }
        for(int i=candidates.length-1;i>=0;i--){
            if(candidates[i]>target || candidates[i] > max){
                continue;
            }
            if(candidates[i]<=target){
                numS.add(candidates[i]);
                dfs(candidates,target-candidates[i],candidates[i],numS,resList);
                numS.removeLast(); 
            }
        }
    }
}
